It has been shown in \cite{Lan13-1} that the accelerated prox-level (APL)method and its variant, the uniform smoothing level (USL) method, have optimaliteration complexity for solving black-box and structured convex programmingproblems without requiring the input of any smoothness information. However,these algorithms require the assumption on the boundedness of the feasible setand their efficiency relies on the solutions of two involved subproblems. Thesehindered the applicability of these algorithms in solving large-scale andunconstrained optimization problems. In this paper, we first present a genericalgorithmic framework to extend these uniformly optimal level methods forsolving unconstrained problems. Moreover, we introduce two new variants oflevel methods, i.e., the fast APL (FAPL) method and the fast USL (FUSL) method,for solving large scale black-box and structured convex programming problemsrespectively. Both FAPL and FUSL enjoy the same optimal iteration complexity asAPL and USL, while the number of subproblems in each iteration is reduced fromtwo to one. Moreover, we present an exact method to solve the only subproblemfor these algorithms. As a result, the proposed FAPL and FUSL methods haveimproved the performance of the APL and USL in practice significantly in termsof both computational time and solution quality. Our numerical results onsolving some large-scale least square problems and total variation based imagereconstruction have shown great advantages of these new bundle-level typemethods over APL, USL, and some other state-of-the-art first-order methods.
展开▼
